package com.leetcode.algorithm.y19.m11;

import java.util.ArrayList;
import java.util.List;

/**
 * 
 * (done)1252. 奇数值单元格的数目
 * (done)1260. 二维网格迁移
 * (done)1266. 访问所有点的最小时间
 * 
 * @author jie.deng
 * @time 2019年11月29日 上午8:55:08
 */
public class MySolution1130 {
	/**
	 * (done)1252. 奇数值单元格的数目
	 * 
     * 给你一个 n 行 m 列的矩阵，最开始的时候，每个单元格中的值都是 0。
     * 
     * 另有一个索引数组 indices，indices[i] = [ri, ci] 中的 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。
     * 
     * 你需要将每对 [ri, ci] 指定的行和列上的所有单元格的值加 1。
     * 
     * 请你在执行完所有 indices 指定的增量操作后，返回矩阵中 「奇数值单元格」 的数目。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 
     * 
     * 输入：n = 2, m = 3, indices = [[0,1],[1,1]]
     * 输出：6
     * 解释：最开始的矩阵是 [[0,0,0],[0,0,0]]。
     * 第一次增量操作后得到 [[1,2,1],[0,1,0]]。
     * 最后的矩阵是 [[1,3,1],[1,3,1]]，里面有 6 个奇数。
     * 示例 2：
     * 
     * 
     * 
     * 输入：n = 2, m = 2, indices = [[1,1],[0,0]]
     * 输出：0
     * 解释：最后的矩阵是 [[2,2],[2,2]]，里面没有奇数。
     *  
     * 
     * 提示：
     * 
     * 1 <= n <= 50
     * 1 <= m <= 50
     * 1 <= indices.length <= 100
     * 0 <= indices[i][0] < n
     * 0 <= indices[i][1] < m
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/cells-with-odd-values-in-a-matrix
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
	 * @param n
	 * @param m
	 * @param indices
	 * @return
	 */
	public int oddCells(int n, int m, int[][] indices) {
		int[] rows = new int[n];
		int[] cols = new int[m];
		for (int i = 0; i < indices.length; i++) {
			rows[indices[i][0]] = rows[indices[i][0]] ^ 1;
			cols[indices[i][1]] = cols[indices[i][1]] ^ 1;
		}
		int rowCnt = 0;
		for (int i = 0; i < rows.length; i++) {
			if (rows[i] == 1) {
				rowCnt++;
			}
		}
		int colCnt = 0;
		for (int i = 0; i < cols.length; i++) {
			if (cols[i] == 1) {
				colCnt++;
			}
		}
		return rowCnt * m + colCnt * n - 2 * rowCnt * colCnt;
	}
    
    /**
     * (done)1260. 二维网格迁移
     * 
     * 给你一个 n 行 m 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。
     * 
     * 每次「迁移」操作将会引发下述活动：
     * 
     * 位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
     * 位于 grid[i][m - 1] 的元素将会移动到 grid[i + 1][0]。
     * 位于 grid[n - 1][m - 1] 的元素将会移动到 grid[0][0]。
     * 请你返回 k 次迁移操作后最终得到的 二维网格。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 
     * 
     * 输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
     * 输出：[[9,1,2],[3,4,5],[6,7,8]]
     * 示例 2：
     * 
     * 
     * 
     * 输入：grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
     * 输出：[[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]
     * 示例 3：
     * 
     * 输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
     * 输出：[[1,2,3],[4,5,6],[7,8,9]]
     *  
     * 
     * 提示：
     * 
     * 1 <= grid.length <= 50
     * 1 <= grid[i].length <= 50
     * -1000 <= grid[i][j] <= 1000
     * 0 <= k <= 100
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/shift-2d-grid
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param grid
     * @param k
     * @return
     */
	public List<List<Integer>> shiftGrid(int[][] grid, int k) {
		int n = grid.length;
		int m = grid[0].length;
		int[][] gridNew = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				gridNew[(i + (j + k) % m) % n][(j + k) % m] = grid[i][j];
//				System.out.println(String.format("gridNew[%s][%s]=grid[%s][%s]", (i + (k + i) / n) % n, (j + k) % m, i ,j));
			}
		}
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		for (int i = 0; i < n; i++) {
			List<Integer> rowList = new ArrayList<Integer>();
			for (int j = 0; j < m; j++) {
				rowList.add(gridNew[i][j]);
			}
			list.add(rowList);
		}
		return list;
	}
    
    /**
     * (done)1266. 访问所有点的最小时间
     * 
     * 平面上有 n 个点，点的位置用整数坐标表示 points[i] = [xi, yi]。请你计算访问所有这些点需要的最小时间（以秒为单位）。
     * 
     * 你可以按照下面的规则在平面上移动：
     * 
     * 每一秒沿水平或者竖直方向移动一个单位长度，或者跨过对角线（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。
     * 必须按照数组中出现的顺序来访问这些点。
     *  
     * 
     * 示例 1：
     * 
     * 
     * 
     * 输入：points = [[1,1],[3,4],[-1,0]]
     * 输出：7
     * 解释：一条最佳的访问路径是： [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   
     * 从 [1,1] 到 [3,4] 需要 3 秒 
     * 从 [3,4] 到 [-1,0] 需要 4 秒
     * 一共需要 7 秒
     * 示例 2：
     * 
     * 输入：points = [[3,2],[-2,2]]
     * 输出：5
     *  
     * 
     * 提示：
     * 
     * points.length == n
     * 1 <= n <= 100
     * points[i].length == 2
     * -1000 <= points[i][0], points[i][1] <= 1000
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/minimum-time-visiting-all-points
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param points
     * @return
     */
	public int minTimeToVisitAllPoints(int[][] points) {
		int paths = 0;
		for (int i = 1; i < points.length; i++) {
			paths += Math.max(Math.abs(points[i][0] - points[i - 1][0]), Math.abs(points[i][1] - points[i - 1][1]));
		}
		return paths;
	}
}
